package com.最小k个数;

import java.util.ArrayList;

public class Solution {

	public int Partition(int a[], int low, int high) {
		int core = a[low];// 设置基准
		int i = low, j = high;
		while (i < j) {
			while (i < j && a[j] >= core)
				j--;
			while (i < j && a[i] <= core)
				i++;
			if (i < j) {
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		// i==j时候交换基准
		a[low] = a[j];
		a[j] = core;
		return i;
	}

	public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		if (input.length < 1 || k <=0 || k > input.length)
			return list;
		int start = 0;
		int end = input.length - 1;
		int index = Partition(input, start, end);
		while (index != k - 1) {
			if (index > k - 1) {
				end = index - 1;
				index = Partition(input, start, end);
			}
			if (index < k - 1) {
                start = index+1;
                index =  Partition(input, start, end);
			}
		}

		for (int i = 0; i <=index; i++) {
			list.add(input[i]);
		}
		return list;
	}

}
